# 定义一个表的类
class Node():
    def __init__(self, value = None, next = None):
        self._value = value
        self._next = next


    def getValue(self):
        return self._value
    

    def getNext(self):
        return self._next


    def setValue(self, new_value):
        self._value = new_value

    
    def setNext(self, new_next):
        self._next = new_next

    
# 实现 Linked List 及其操作方法
class LinkedList():
    def __init__(self):
        self._head = Node()
        self._tail = None
        self._length = 0

    
    # 检测是否为空
    def isEmpty(self):
        return self._head == None

    
    # add 在链表尾添加元素：头插法：O(1)
    def add(self, value):
        newnode = Node(value, None)         # create 一个 node （为了插入一个链表）
        newnode.setNext(self._head)
        self._head = newnode


    # append 在链表尾部插入一个元素：尾插法 O(n)
    def append(self, value):
        newNode = Node(value)
        if self.isEmpty():
            self._head = newNode        # 若为空表，将添加的元素设为第一个元素
        else:
            current = self._head
            while current.getNext() != None:
                current = current.getNext()     # 遍历链表
            current.setNext(newNode)            # 此时 current 为链表最后的元素

    
    # search 检查元素是否在链表中
    def search(self, value):
        current = self._head
        foundvalue = False
        while current != None and not foundvalue:
            if current.getValue() == value:
                foundvalue = True
            else:
                current = current.getNext()
        return foundvalue

    
    # index 索引元素在链表中的位置
    def index(self, value):
        current = self._head
        count = 0
        found = None
        while current != None and not found:
            count += 1
            if current.getValue() == value:
                found = True
            else:
                current = current.getNext()
        if found:
            return count
        else:
            raise ValueError("%s is not in linkedlist" % value)
    

    # remove 删除链表中的某项元素
    def remove(self, value):
        current = self._head
        pre = None
        while current != None:
            if current.getValue() == value:
                if not pre:
                    self._head = current.getNext()
                else:
                    pre.setNext(current.getNext())
                break
            else:
                pre = current
                current = current.getNext()

    
    # insert 链表中插入元素
    def insert(self, pos, value):
        if pos <= 1:
            self.add(value)
        elif pos > self.size():
            self.append(value)
        else:
            temp = Node(value)
            count = 1
            pre = None
            current = self._head
            while count < pos:
                count += 1
                pre = current
                current = current.getNext()
            pre.setNext(temp)
            temp.setNext(current)
    

    # printf 打印链表
    def printf(self):
        answer = []

        current = self._head
        while current:
            answer.append(current.getValue())
            current = current.getNext()
        
        for ans in answer:
            print(ans)


def main():
    L = LinkedList()
    L.append(0)
    L.append(1)
    L.append(2)
    L.append(3)
    L.printf()
    print("====================")
    L.remove(2)
    L.printf()




if __name__ == '__main__':
    main()
    